package com.zp.self.module.level_4_算法练习.数据结构.二叉树.平衡二叉树;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ：zengpeng
 * @date ：Created 2022/6/1 8:37
 * 鸣谢：https://mp.weixin.qq.com/s/dYP5-fM22BgM3viWg4V44A   --但代码实现有问题【左右、右左】代码bug.也挺好.自己改好了就说明掌握了
 */
public class 平衡二叉树_插入_构建 {

    @Test
    public void testBuildAVL() {

        int[] arr = new int[]{1, 4, 5, 6, 7, 10, 9, 8, 23, 2, 13, 32, 321, 32, 321, 312, 321, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 3, 23, 2};
        AvlNode node = buildAVL(arr);
        System.out.println(node);
    }

    /**
     题目：根据数组构建平衡二叉树

     分析：构建步骤如下：
             方案一：平衡二叉树旋转构建
                 1.递归遍历找到插入点
                 2.回溯，判断左右子树高度是否==2
                 3.根据4种情况，旋转二叉树，保证平衡
                     a、左左：右旋
                     b、右右：左旋
                     c、左右：左右 --左旋【左孩子】，右旋自己
                     d、右左：右左 --右旋【右孩子】，左旋自己
             方案二：排序数组，二分法构建
     **/
    public static AvlNode buildAVL(int[] arr) {
        AvlNode node = null;
        //构建平衡二叉树
        Map<AvlNode,Integer> map = new HashMap<>();
        for (int num : arr){
            node = insert(node, num);
            map.clear();
            System.out.println("插入:"+num +"后,是否还是AVL: "+平衡二叉树_验证.isAVL(node,map));
        }
        return node;
    }

    /**
     * Description: 插入节点
     */
    public static AvlNode insert(AvlNode node, int numb) {
        if (node == null)
            return new AvlNode(numb, 1);
        if (numb > node.data) {
            node.rchild = insert(node.rchild, numb);
            if (height(node.rchild) - height(node.lchild) == 2) {//如果子树 高度不平衡，则当前节点需要旋转
                if (numb > node.rchild.data) {
                    //右右： 左旋
                    node = L_Rotate(node);
                } else {
                    //右左 ： 先对右旋【右孩子】，再左旋自己
                    node = R_L_Rotate(node);
                }
            }
        } else {
            node.lchild = insert(node.lchild, numb);
            if (height(node.lchild) - height(node.rchild) == 2) {//如果子树 高度不平衡，则当前节点需要旋转
                if (numb > node.lchild.data) {
                    //左右: 先对左旋【左孩子】，再右旋自己
                    node = L_R_Rotate(node);
                } else {
                    //左左: 右旋
                    node = R_Rotate(node);
                }
            }
        }
        node.height = Math.max(height(node.lchild), height(node.rchild)) + 1;
        return node;
    }

    /**
     * Description: 右左 ：先对右旋【右孩子】，再左旋自己
     */
    public static AvlNode R_L_Rotate(AvlNode node) {
        node.rchild = R_Rotate(node.rchild);
        node = L_Rotate(node);
        return node;
    }

    /**
     * Description: 左右: 先对左旋【左孩子】，再右旋自己
     */
    public static AvlNode L_R_Rotate(AvlNode node) {
        node.lchild = L_Rotate(node.lchild);
        node = R_Rotate(node);
        return node;
    }

    /**
     * Description: 左旋
     */
    public static AvlNode L_Rotate(AvlNode node) {
        AvlNode rChild = node.rchild;
        node.rchild = rChild.lchild;
        rChild.lchild = node;

        node.height = Math.max(height(node.lchild), height(node.rchild)) + 1;
        rChild.height = Math.max(height(rChild.lchild), height(rChild.rchild)) + 1;
        return rChild;
    }

    /**
     * Description: 右旋
     */
    public static AvlNode R_Rotate(AvlNode node) {
        AvlNode lChild = node.lchild;
        node.lchild = lChild.rchild;
        lChild.rchild = node;

        node.height = Math.max(height(node.lchild), height(node.rchild)) + 1;
        lChild.height = Math.max(height(lChild.lchild), height(lChild.rchild)) + 1;

        return lChild;
    }

    /**
     * Description: 获取节点高度
     */
    public static int height(AvlNode node) {
        return node == null ? 0 : node.height;
    }
}
